package com.banyiyi.simple.pattern.algroithm;

import java.util.*;

/**
 * @ClassName BucketSort
 * @Description 桶排序
 * @Author yangwm
 * @Date 2023/2/9 16:42
 * @Version 1.0
 */
public class BucketSort {

    public static void main(String[] args) {
        double[] a = new double[]{1.4,2.4,2,0.8,2.0,3.0,5.9,4.4,3.1};
        double[] doubles = bucketSort(a);
        PrimitiveIterator.OfDouble iterator = Arrays.stream(doubles).iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.nextDouble());
        }
    }


    private static double[] bucketSort(double[] a){
        // 判空
        if(a.length == 0) return a;
        // 首先指定固定分段数
        int t = 2;
        // 获取最大值
        double max = a[0];
        double min = a[0];
        for (int i = 1; i < a.length; i++) {
            max = Math.max(max,a[i]);
            min = Math.min(min,a[i]);
        }
        // 求桶的个数
        int num = a.length;
        // 创建桶
        ArrayList<LinkedList<Double>> list = new ArrayList<LinkedList<Double>>(num);
        for (int j = 0; j < num; j++) {
            list.add(new LinkedList<Double>());
        }
        // 向桶中装入元素，并排序
        for (int i = 0; i < a.length; i++) {
            // 元素放桶的位置
            int index = (int) Math.floor((a[i] - min) * (num - 1) / (max - min));
            list.get(index).add(a[i]);
        }
        // 每个桶排序并输出
        double[] sort = new double[a.length];
        int index = 0;
        int count = 0;
        for (LinkedList<Double> doubles : list) {
            count++;
            Collections.sort(doubles);
            for (Double aDouble : doubles) {
                sort[index++] = aDouble;
                System.out.println(count+"桶中元素包含"+aDouble);
            }
            System.out.printf("第 {%s} 桶--------------------------------------------- %n",count);
        }
        return sort;
    }



}
